docs/Brent's reorganization scheme insertion.htm

   1 <HEAD>
   2 <TITLE>Brent's reorganization scheme: insertion
   3 </TITLE>
   4 <BODY>
   5 <H2>
   6 <H3>
   7 <A HREF="../../images/handbook.gif"><IMG SRC="../../images/handbook2.gif" align=left></A>
   8 <A HREF="../../hbook.html">
   9 <IMG SRC="../../images/home_g.gif" hspace = 15 vspace = 4 ALT = "[Home]"></A><BR>
  10 <A HREF="../../search_a.html">
  11 <IMG SRC="../../images/chapter_g.gif" hspace = 15 vspace = 4 ALT = "[Chapter]"></A><BR>
  12 <A HREF="../../expand.html">
  13 <IMG SRC="../../images/contents_g.gif" hspace = 15 vspace = 4 ALT = "[Contents]"></A><BR>
  14 <A HREF="3381.ins.c.html">
  15 </A>
  16 <A HREF="3381.ins.c.html">
  17 <IMG SRC="../../images/prevalg_g.gif" hspace = 15 vspace = 4 ALT = "[Previous Algorithm]"></A><BR>
  18 <A HREF="341.data.c.html">
  19 <IMG SRC="../../images/nextalg_g.gif" hspace = 15 vspace = 4 ALT = "[Next Algorithm]"></A><BR>
  20 <BR></H2>
  21 <HR>
  22 <H2><B>Brent's reorganization scheme: insertion
  23 </B></H2><BR>
  24 <CENTER>
  25 <TABLE BORDER>
  26 <TR>
  27 <TD COLSPAN = 1>
  28 <TD rowspan = 1>
  29 <TR><TD>
  30 <XMP>
  31      procedure insert( key : typekey; var r : dataarray );
  32      label 999;
  33      var i, ii, inc, init, j, jj : integer;
  34
  35      begin
  36      init := hashfunction( key );
  37      inc  := increment( key );
  38      for i:=0 to n do
  39           for j:=i downto 0 do begin
  40                jj := (init + inc*j) mod m;
  41                ii := (jj + increment(r[jj].k) * (i-j)) mod m;
  42                if empty(r[ii]) or deleted(r[ii]) then begin
  43                     {*** move record forward ***}
  44                     r[ii] := r[jj];
  45                     {*** insert new in r[jj] ***}
  46                     r[jj].k := key;
  47                     n := n+1;
  48                     goto 999  {*** return ***}
  49                     end
  50                end;
  51      Error {*** table full ***};
  52      999:
  53      end;
  54 </XMP></TD></TR></TABLE>
  55 <BR>
  56 <H3><A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/3381.ins.c"><IMG SRC="../../images/ftp.xbm" hspace=10>C</A> source (3381.ins.c)  <A HREF="ftp://sunsite.dcc.uchile.cl/pub/users/rbaeza/handbook/algs/3/3381.ins.p"><IMG SRC="../../images/ftp.xbm" hspace=10>Pascal</A> source (3381.ins.p)
  57 </H3></CENTER>
  58 <HR><H4>
  59 <IMG SRC="../../images/aw3.gif" align=left><H5><BR>
  60 &copy <A HREF="http://aw.com">Addison-Wesley </A>Publishing Co. Inc.
  61 </H5></H4><HR>
  62 </BODY>